package com.algorithm.cn.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 
 * @author wangzonghui
 * @date 2021-01-20 22:12:16
 * @Description: 冒泡排序代码实现
 * 冒泡排序的时间复杂度为两个for循环
 */
public class BubbleSort {

	public static void main(String[] args) {
//		int arr[]= {3,9,-1,10,-2};
		
		int size=80000;
		int[] arr=new int[size];
		for(int i=0;i<80000;i++) {
			arr[i]=(int) (Math.random()*size);
		}
		
		//为了容易理解，把冒泡排序的演变过程展示出来
		//第一次，把最大的排到最后
		Date start=new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		System.out.println("排序前时间:"+simpleDateFormat.format(start));
		bubbleSort(arr);
		System.out.println("排序后时间:"+simpleDateFormat.format(new Date()));
//		System.out.println("排序后:"+Arrays.toString(arr));
		
	}
	
	public static void bubbleSort(int [] arr) {
		int temp=0;
		boolean flag=false;  //表示是否进行过交换
		for(int i=0,length=arr.length-1;i<length;i++) {
			
			for(int j=0;j<arr.length-1-i;j++) {
				if(arr[j]> arr[j+1]) {
					flag=true;
					temp=arr[j];
					arr[j]=arr[j+1];
					arr[j+1]=temp;
				}
			}
//			System.out.println("第"+(i+1)+"次后数组："+Arrays.toString(arr));
			
			//优化 一次未发生交换就退出
			if (!flag){  //交换一次都未发生
				break;
			}else {
				flag=false;
			}
		}
	}

}
